﻿//
// Created by qi on 24-5-20.
//

#ifndef AVLTREE_H
#define AVLTREE_H

typedef struct AvlTree AvlTree;
typedef struct TreeNode TreeNode;

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//可能用到的最大的堆栈高度
#define MAX_STACK_HIGH 50

//二叉树节点
struct TreeNode {
    void* data;//数据指针
    unsigned char bf;//平衡因子
    unsigned char height;//节点高度
    TreeNode *left,*right;//左右指针
};

//AVL二叉树
struct AvlTree {
    size_t node_count;//节点数量
    unsigned char height;//树高
    TreeNode* head;//树的头节点
};


//使用堆栈时，AVL树的迭代器
typedef struct AvlIterator {
    //双向堆栈
    TreeNode* stack_tow_way[MAX_STACK_HIGH];

    //栈两边的高度
    unsigned char stack_next_len,stack_prev_len;

    //迭代的状态，0表示正常，1表示当前节点位于最大节点之后
    //-1表示当前节点位于最小节点之前
    unsigned char status;

    //当前节点的高度
    unsigned char cur_height;

    //当前所指节点
    TreeNode *cur_node;
}AvlIterator;

/**
 * 插入一个节点到AVL树中
 * @param tree 需要插入节点的树指针
 * @param data 插入的数据地址
 * @param data_len 插入的数据的长度
 * @param cmp 比较插入节点的树中节点大小的指针,第一个形参表示新的数据节点
 *    第二个形参表示树中的节点的数据指针
 * @return 新插入的或已经存在的节点的指针，返回NULL表示插入失败
 */
void* insert_avltree(AvlTree* tree,void* data,size_t data_len,int(*cmp)(void*,void*));

/**
 * 从AVL树中删除一个节点，并返回对应的数据指针（不负责数据内存的释放）
 * @param tree 需要删除节点的树指针
 * @param data 用于查找树中节点的数据指针
 * @param cmp 比较data和树中节点数据大小的函数，第一个形参是data
 *    第二个形参是树中的节点数据指针
 * @return 成功删除返回数据指针，否则返回NULL
 */
void* delete_node_avltree(AvlTree* tree,void* data,int(*cmp)(void*,void*));

/**
 * 从树中查找符合条件的节点
 * @param tree 需要查找节点的树指针
 * @param data 用于查找树中节点的数据指针
* @param cmp 比较data和树中节点数据大小的函数，第一个形参是data
 *    第二个形参是树中的节点数据指针
 * @return 成功找到返回节点的数据指针，否则返回NULL
 */
void* find_avltree(AvlTree* tree,void* data,int(*cmp)(void*,void*));

/**
 * 销毁整个AVL树的内部数据
 * @param tree 需要销毁数据的二叉树指针
 * @param is_free 是否需要销毁节点的数据指针，0表示不用，非0表示要
 */
void destroy_avltree(AvlTree* tree,int is_free);

/**
 * 初始化一颗树的信息
 * @param tree 需要初始化信息的树
 */
void init_avltree(AvlTree* tree);


/**
 * 初始化avl树的迭代器
 * @param tree Avl树的指针
 * @param iterator 迭代器的指针
 * @param begin_direction 初始的位置，0表示在avl树的最小值节点开始，
 *  非0表示在avl树的最大值节点开始
 */
void init_iterator_avltree(AvlTree* tree,AvlIterator* iterator,int begin_direction);

/**
 * 返回当前迭代器所指向的下一个位置
 * @param iterator 迭代器的指针
 * @return 如果下一个位置存在数据，那么返回下一个节点的数据指针
 *  否则返回NULL
 */
void* next_avltree(AvlIterator* iterator);

/**
 * 返回当前迭代器所指向的前一个位置
 * @param iterator 迭代器的指针
 * @return 如果下一个位置存在数据，那么返回前一个节点的数据指针
 *  否则返回NULL
 */
void* prev_avltree(AvlIterator* iterator);

/**
 * 从二叉树中查找一个节点，并返回该节点的迭代器
 * @param tree 需要查找的二叉树
 * @param data 待比较的数据指针
 * @param cmp 比较data和树中节点数据大小的函数，第一个形参是data
 *    第二个形参是树中的节点数据指针
 * @param iterator 用于接收查找结果的迭代器指针
 * @return 查找成功返回节点的数据指针，失败返回NULL
 */
void* find_into_iterator_avltree(AvlTree* tree,void* data,int(*cmp)(void*,void*),AvlIterator* iterator);


#endif //AVLTREE_H
